package interview.huawei.training.p50;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * 字符串版本，可以处理超过2位数的计算，可以将相连的几个数字字符解析成一个数字
 */
public class Main3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 中缀表达式转后缀表达式
        ArrayList<String> postfixList = infixToPostfix(scanner.nextLine());
        // System.out.println(postfixList);
        // 根据后缀表达式计算结果
        ArrayDeque<String> stack = new ArrayDeque<>();
        for (String s : postfixList) {
            if (s.equals("+")) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                // 计算结果再入栈
                stack.push((num2 + num1) + "");
            }
            else if (s.equals("-")) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                // 计算结果再入栈
                stack.push((num2 - num1) + "");
            }
            else if (s.equals("*")) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                // 计算结果再入栈
                stack.push((num2 * num1) + "");
            }
            else if (s.equals("/")) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                // 计算结果再入栈
                stack.push((num2 / num1) + "");
            }
            // 数字直接入栈
            else {
                stack.push(s);
            }
        }
        System.out.println(stack.pop());
    }

    // 中缀表达式转后缀表达式
    private static ArrayList<String> infixToPostfix(String infixStr) {
        StringBuilder sb = new StringBuilder();
        // 在所有的加减乘除以及括号的前后加上逗号，然后再split一下，就可以将数字和运算符拆出来
        for (int i = 0; i < infixStr.length(); i++) {
            char ch = infixStr.charAt(i);
            if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' ||
               ch == ')' || ch == '[' || ch == ']' || ch == '{' || ch == '}') {
                sb.append(',');
                sb.append(ch);
                sb.append(',');
            } else {
                sb.append(ch);
            }
        }
        // System.out.println(sb);
        // 如：
        // 3+2*{1+2*[-40/(18-6)+7]}
        // 加上逗号以后变成：
        // 3,+,2,*,,{,1,+,2,*,,[,,-,40,/,,(,18,-,6,),,+,7,],,},
        // split后的数组还需要过滤掉空串
        String[] infixArray = sb.toString().split(",");
        // 双指针，i指向从左往右第一个空的位置，j遍历元素
        int j = 0;
        for (; j < infixArray.length; j++) {
            if (infixArray[j].length() == 0) {
                break;
            }
        }
        for (int i = j + 1; i < infixArray.length; i++) {
            if (infixArray[i].length() > 0) {
                infixArray[j++] = infixArray[i];
            }
        }
        // j就是过滤掉空串后数组中实际元素的个数

        ArrayList<String> infixList = new ArrayList<>();
        // 解决负数的问题，如 -1 + 1
        // 即在 -1 前面加一个0 变成  0-1 即可
        // 情况1：第1个字符是负号
        String s = infixArray[0];
        if (s.equals("-")) {
            infixList.add("0");
        }
        infixList.add(s);
        // 情况2：( [ { 等字符后面是负号
        for (int i = 1; i < j; i++) {
            s = infixArray[i];
            // 过滤掉空串
            if (s.length() > 0) {
                String preS = infixArray[i - 1];
                // 上一次字符是括号，当前字符为减号，前面补个0
                if ((preS.equals("(") || preS.equals("[") || preS.equals("{")) && s.equals("-")) {
                    infixList.add("0");
                }
                infixList.add(s);
            }
        }
        // System.out.println(infixList);

        // 将中缀表达式转成后缀表达式
        ArrayList<String> postfixList = new ArrayList<>();
        // 符号栈
        ArrayDeque<String> signStack = new ArrayDeque<>();
        for (String ch : infixList) {
            String topSign = signStack.peek();
            switch (ch) {
                case "+":
                case "-":
                    // 如果符号栈的栈顶元素的优先级不低于当前运算符
                    // 栈顶元素出栈后放进后缀表达式数组中
                    while (!signStack.isEmpty() && (topSign.equals("*") || topSign.equals("/") || topSign.equals("+") || topSign.equals("-"))) {
                        postfixList.add(signStack.pop());
                        topSign = signStack.peek();
                    }
                    // 将加减符号放进符号栈
                    signStack.push(ch);
                    break;
                case "*":
                case "/":
                    // 如果符号栈的栈顶元素的优先级不低于当前运算符
                    // 栈顶元素出栈后放进后缀表达式数组中
                    while (!signStack.isEmpty() && (topSign.equals("*") || topSign.equals("/"))) {
                        // */的优先级不低于当前运算符，所以要出栈，加减的优先级低于当前运算符，不予处理
                        postfixList.add(signStack.pop());
                        topSign = signStack.peek();
                    }
                    // 将乘除符号放进符号栈
                    signStack.push(ch);
                    break;
                case "(":
                case "[":
                case "{":
                    // 遇到左括号直接加入符号栈
                    signStack.push(ch);
                    break;
                case ")":
                    // 遇到右括号，一直出栈直到匹配到左括号，且当前右括号不入符号栈
                    topSign = signStack.pop();
                    while (!signStack.isEmpty() && !topSign.equals("(")) {
                        postfixList.add(topSign);
                        topSign = signStack.pop();
                    }
                    break;
                case "]":
                    // 遇到右括号，一直出栈直到匹配到左括号，且当前右括号不入符号栈
                    topSign = signStack.pop();
                    while (!signStack.isEmpty() && !topSign.equals("[")) {
                        postfixList.add(topSign);
                        topSign = signStack.pop();
                    }
                    break;
                case "}":
                    // 遇到右括号，一直出栈直到匹配到左括号，且当前右括号不入符号栈
                    topSign = signStack.pop();
                    while (!signStack.isEmpty() && !topSign.equals("{")) {
                        postfixList.add(topSign);
                        topSign = signStack.pop();
                    }
                    break;
                default: postfixList.add(ch);
            }
        }

        while(!signStack.isEmpty()) {
            postfixList.add(signStack.pop());
        }

        return postfixList;
    }
}